什么是动态数组

动态数组是一种数据结构，它的容量可以根据需要动态扩展或收缩。与固定大小的数组不同，动态数组在运行时可以调整其大小，以容纳更多的元素或节省空间。这使得动态数组在需要频繁添加或删除元素的应用场景中非常有用。

动态数组的特点

自动调整大小：

当动态数组的容量不足以容纳新元素时，它会自动扩展。这通常通过分配一个更大的新数组并将旧数组的元素复制到新数组中来实现。
扩展的方式通常是按比例增加容量，例如，每次扩展时将容量增加一倍或增加一个固定的百分比。这种策略可以确保平均情况下插入操作的时间复杂度仍然是 O(1)。

随机访问：

动态数组允许通过索引进行 O(1) 时间复杂度的随机访问，因为它底层是基于连续内存块实现的数组。

动态缩小：

一些动态数组实现还支持在元素删除后动态缩小容量，以节省内存。

动态数组的实现

在 Java 中，ArrayList 就是一个典型的动态数组实现。下面是一个简单的动态数组的实现示例：

import java.util.Arrays;

public class DynamicArray {
    private int[] array;
    private int size;

    public DynamicArray() {
        array = new int[10];
        size = 0;
    }

    public void add(int element) {
        if (size == array.length) {
            resize();
        }
        array[size++] = element;
    }

    public int get(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return array[index];
    }

    private void resize() {
        int newSize = array.length * 2;
        array = Arrays.copyOf(array, newSize);
    }

    public int size() {
        return size;
    }
}

详细说明

初始化：

array 初始化为一个大小为 10 的数组。
size 用于跟踪数组中元素的个数。

添加元素：

在 add 方法中，如果当前数组已满（size == array.length），则调用 resize 方法将数组容量扩展为原来的两倍。
将新元素添加到数组的末尾，并增加 size。

访问元素：

在 get 方法中，通过索引访问元素。如果索引超出范围，则抛出 IndexOutOfBoundsException 异常。

调整大小：

在 resize 方法中，使用 Arrays.copyOf 方法创建一个新的数组，并将旧数组的元素复制到新数组中。

动态数组的优缺点

优点：

动态调整大小，适应变化的存储需求。 支持 O(1) 时间复杂度的随机访问。

缺点：

在扩展数组时，需要进行元素的复制操作，可能导致暂时的性能下降。
对于频繁的插入和删除操作，特别是在数组中间位置，性能不如链表。

总之，动态数组是一种灵活且高效的数据结构，适用于需要随机访问和动态调整大小的场景。